package com.wangzh.data.arithmetic.recursion;

import java.util.LinkedList;

//汉诺塔问题  移动圆盘
public class HanoiTower {
    static LinkedList<Integer> a = new LinkedList<>();
    static LinkedList<Integer> b = new LinkedList<>();
    static LinkedList<Integer> c = new LinkedList<>();

    public static void main(String[] args) {

        init(64);
        print();
        move(64,a,b,c);

    }

    /**
     *
     * @param n 圆盘个数
     * @param a  源
     * @param b 借
     * @param c 目
     *T(n)=2*T(n-1)+c,T(1)=c
     *      T(2)=2*T(1)+c=3*c
     *      T(3)=2*T(2)+c=2*(3c)+c=6c+c
     *
     *          整体替代逻辑 n-1为一个整体，比如  2，1为一个整体  3， 【2，1】
     */
    static void move(int n,LinkedList<Integer> a,
                     LinkedList<Integer> b,
                     LinkedList<Integer> c){
        if (n==0){
            return;
        }
        move(n-1,a,c,b); //把整体先移动到借用 的链表
        c.addLast(a.removeLast());//将最后一个值移动到借用的链表
        print();
        move(n-1,b,a,c);//将放到借用链表的整体移动到目的链表
    }
    static void init(int n){
        for (int i = n; i >=1; i--) {
            a.addLast(i);
        }
    }

    static void print(){
        System.out.println("-----------------------");
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }
}
